using namespace std;
#include<iostream>
#include<vector>

//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums)
//    {
//        vector<vector<int>> ret;
//        sort(nums.begin(), nums.end());
//
//        int n = nums.size();
//        for (int cur = 0; cur < n;)
//        {
//            int left = cur + 1, right = n - 1;
//            int target = -nums[cur];
//            while (left < right)
//            {
//                int sum = nums[left] + nums[right];
//
//                if (nums[cur] > 0) break;
//                if (sum < target)
//                {
//                    left++;
//                }
//                else if (sum > target)
//                {
//                    right--;
//                }
//                else
//                {
//                    ret.push_back({ nums[cur],nums[left],nums[right] });
//                    left++;
//                    right--;
//                    while (left < right && nums[left] == nums[left - 1])
//                    {
//                        left++;
//                    }
//                    while (left < right && nums[right] == nums[right + 1])
//                    {
//                        right--;
//                    }
//                }
//
//            }
//            cur++;
//            while (cur < nums.size() && nums[cur] == nums[cur - 1])
//            {
//                cur++;
//            }
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums)
//    {
//        vector<vector<int>> ret;
//        sort(nums.begin(), nums.end());
//
//        int n = nums.size();
//        for (int cur = 0; cur < n;)
//        {
//            int left = cur + 1, right = n - 1;
//            int target = -nums[cur];
//            while (left < right)
//            {
//                int sum = nums[left] + nums[right];
//
//                if (nums[cur] > 0) break;
//                if (sum < target)
//                {
//                    left++;
//                }
//                else if (sum > target)
//                {
//                    right--;
//                }
//                else
//                {
//                    ret.push_back({ nums[cur],nums[left],nums[right] });
//                    left++;
//                    right--;
//
//                    while (left < right && nums[left] == nums[left - 1]) { left++; }
//                    while (left < right && nums[right] == nums[right + 1]) { right--; }
//                }
//            }
//            cur++;
//            while (cur < nums.size() && nums[cur] == nums[cur - 1]) { cur++; }
//        }
//        return ret;
//    }
//};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());

        int n = nums.size();
        int cur = 0;
       while(cur<n)
       {
           int left = cur + 1, right = n - 1;
           int target = -nums[cur];
           while (left < right)
           {
               int sum = nums[left] + nums[right];

               if (nums[cur] > 0) break;
               if (sum < target)
               {
                   left++;
               }
               else if (sum > target)
               {
                   right--;
               }
               else
               {
                   ret.push_back({ nums[cur],nums[left],nums[right] });
                   left++;
                   right--;

                   while (left < right && nums[left] == nums[left - 1]) { left++; }
                   while (left < right && nums[right] == nums[right + 1]) { right--; }
               }
           }
           cur++;
           while (cur < nums.size() && nums[cur] == nums[cur - 1]) { cur++; }

       }
        return ret;
    }
};